The recognition of the superior quality of digital technologies has resulted in an unprecedented demand for digital products. This is evidenced by the popularity of consumer electronic devices such as audio compact discs, direct broadcast satellite systems, digital video disc (DVD) players, and digital video tape systems, as well as personal computer (PC) peripheral devices such as compact disc read-only memory (CD-ROM) drives, DVD drives, video cameras, musical instrument digital interface (MIDI) devices, and digital scanners.
The popularity of digital devices prompted a need for a uniform digital interface capable of connecting such devices into a single network. Consequently, the Institute of Electrical and Electronics Engineers (IEEE) introduced Standard 1394 titled "IEEE Standard for a High Performance Serial Bus," IEEE Computer Society, Dec. 12, 1995 ("IEEE 1394").
IEEE 1394 enables isochronous service while providing the bandwidth needed for audio, imaging, video, and other streaming data. Isochronous service means it guarantees latency (i.e., the length of time between a requested action and when the resulting action occurs). Latency is a critical feature in supporting real time video, for example. IEEE 1394 provides a high-speed serial bus with data transfer rates of 100, 200, or 400 mega-bits per second.
It is well-known in the art that IEEE 1394 data transfer rates can be improved by optimizing a parameter referred to as a "gap count." If the gap count is set too low, timing based arbitration breaks down. For instance, some nodes may detect idle time as an arbitration reset gap before others detect a subaction gap. The smaller the gap count is set, the smaller the bus topology must be for the timing to work. If the gap count is set too high, arbitration works, but the bus efficiency suffers from the larger than necessary gaps. Consequently, it is a design goal for IEEE 1394 network designers to set the gap count to the lowest workable value for a particular topology without interfering with the timing of the network.
One technique for determining an optimum gap count for a particular serial bus network is described in Annex E of IEEE 1394 itself. Table E-6 of Annex E lists predefined gap counts based upon the longest chain of nodes bounded by a pair of end nodes ("longest daisy chain") in the network, which is often measured in terms of "hops." For example, a serial bus network having seven nodes in its longest daisy-chain would have a total of six hops, which according to Table E-6 merits a gap count of six. Various techniques exist for determining the number of hops in a network. For example, "self-ID" packets sent by each node can be used to reconstruct the topology of a bus network, or the bus manager can simply assume a maximum number of hops (16) for a given network.
A gap count derived using Table E-6 and the various methods for determining hops, however, is unsatisfactory for at least one major reason. Of particular importance in optimizing a gap count is ascertaining a maximum round trip propagation delay for sending a packet of information from one end node to another end node for a given daisy-chain. A minimum gap count is then calculated using the longest round trip propagation delay found in the network, among various other factors. Table E-6 lists a maximum round trip propagation delay for a given number of hops based on the assumption that the length of the transmission medium (e.g., co-axial cable) between each node is 4.5 meters. The actual length of each cable, however, could range as high as 100 meters or more. Therefore, the maximum round trip propagation delay assumed by Table E-6 could in practice be far less than what is actually incurred in a network. As a result, the gap count derived using Table E-6 could be set low enough to cause timing problems throughout the network.
Bill Duckwall in a paper titled "1394a Enhancements" available at "ftp//ftp.symbios.com" (the "Duckwall reference") suggests calculating a gap count using a maximum round-trip delay measured by "PHY pinging." According to the Duckwall reference, a diagnostic node transmits a special packet containing a target address ("ping packet"). The node starts a timer when transmission is complete. When the target node receives the ping, it sends back a ping response packet. The diagnostic node detects the ping response, stops the timer at start of reception, and calculates from the timer the propagation delay to the target node. The diagnostic node selects the longest delay in the network and sets the gap count accordingly.
The technique disclosed in the Duckwall reference, however, is unsatisfactory for a number of reasons. Foremost, the Duckwall reference assumes the diagnostic node is actually one of the end nodes of the daisy chain having the longest delay in the network. This suggests that each end node must have the appropriate hardware and software to perform PHY pinging. This requirement is expensive and redundant. Further, the Duckwall reference assumes that the measured delay is the maximum propagation delay time. The measured delay, however, is merely representative of a single ping of a particular daisy-chain, and therefore may not represent the worst case delay over that particular daisy-chain without further information.
In view of the foregoing, it can be appreciated that a substantial need exists for a method and apparatus for determining an improved gap count for a given network topology that solves the above-discussed problems.